package jzoffer;

import leetcode.tree.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @author MaoLin Wang
 * @date 2020/10/10 12:04 上午
 */
public class _32层次遍历2 {
    public static List<List<Integer>> levelOrder(TreeNode root) {
        if (root==null){
            return new ArrayList<>();
        }
        List<List<Integer>>arrayList=new ArrayList<>();
        Queue<TreeNode>queue=new LinkedList<>();
        queue.offer(root);
        int level=0;
        //下一层的节点个数
        int count=0;
        List<Integer>temp=null;
        while (!queue.isEmpty()){
            temp=new ArrayList<>();
            //当前层的节点个数 count记录上一层添加到queue的个数，即遍历N层时，用count记录N+1层的节点树，如果下一次有节点，则当前层的节点个数应当是 min(count,2^level)个
            int num= (int) (count==0?Math.pow(2,level):Math.min(count,Math.pow(2,level)));
            count=0;
            for (int i = 0; i <num; i++) {
                if (queue.isEmpty()){
                    break;
                }
                TreeNode node = queue.poll();
                if (node.left!=null){
                    queue.add(node.left);
                    count++;
                }
                if (node.right!=null){
                    queue.add(node.right);
                    count++;
                }
                temp.add(node.val);
            }
            arrayList.add(temp);
            level++;
        }
        return arrayList;
    }

    public static List<List<Integer>> levelOrder2(TreeNode root) {
        if (root==null){
            return new ArrayList<>();
        }
        List<List<Integer>>arrayList=new ArrayList<>();
        Queue<TreeNode>queue=new LinkedList<>();
        queue.offer(root);
        List<Integer>temp=null;
        while (!queue.isEmpty()){
            temp=new ArrayList<>();
            for (int i = queue.size(); i >0; i--) {
                TreeNode node = queue.poll();
                temp.add(node.val);
                if (node.left!=null){
                    queue.add(node.left);
                }
                if (node.right!=null){
                    queue.add(node.right);
                }
            }
            arrayList.add(temp);
        }
        return arrayList;
    }

    public static void main(String[] args) {
        TreeNode treeNode=new TreeNode(1);
        treeNode.left=new TreeNode(2);
        treeNode.right=new TreeNode(3);
        treeNode.left.left=new TreeNode(4);
        treeNode.left.right=new TreeNode(5);
        List<List<Integer>> lists = levelOrder(treeNode);
        System.out.println(lists);
    }
}
